﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;
//给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。
//O(logC)
int getSum(int a, int b)
{
    while (b)
    {
        int i = a ^ b;
        int f = (a & b) << 1;
        a = i;
        b = f;
    }
    return a;
}

//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
//时间: O(NlogC)
int singleNumber(vector<int>& nums)
{
    int ret = 0;
    for (int i = 0; i < 32; i++)
    {
        int num = 0;
        for (int f = 0; f < nums.size(); f++)
        {
            if (((nums[f] >> i) & 1) == 1)
            {
                num++;
            }
        }
        num %= 3;
        if (num == 1) ret |= 1 << i;
    }
    return ret;
}